//! 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

//! 你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
//! 你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
//! 你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

//! 你可以按任意顺序返回答案。

 

//! 示例 1：

//! 输入：nums = [2,7,11,15], target = 9
//! 输出：[0,1]
//! 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
//! 示例 2：

//! 输入：nums = [3,2,4], target = 6
//! 输出：[1,2]
//! 示例 3：

//! 输入：nums = [3,3], target = 6
//! 输出：[0,1]
//! 

use std::collections::HashMap;

struct Solution;

impl Solution {

    /// 方案1，双循环
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        for i in 0..nums.len() {
            for j in i+1..nums.len() {
                if nums[i] + nums[j] == target {
                    return vec![i as i32, j as i32];
                }
            }
        }
        Vec::new()
    }

    /// 方案2，双循环，但是相比上一个会减少一个步骤，计算出剩余数
    pub fn two_sum2(nums: Vec<i32>, target: i32) -> Vec<i32> {
        for i in 0..nums.len() {
            let remain = target - nums[i];
            for j in i+1..nums.len() {
                if nums[j] == remain {
                    return vec![i as i32, j as i32];
                }
            }
        }
        Vec::new()
    }

    /// 方案3，单循环，但是需要提供一个map来作为查询的容器，
    pub fn two_sum3(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut cache = HashMap::<i32, i32>::new();
        for i in 0..nums.len() {
            let remain = target - nums[i];
            if let Some(e) = cache.get(&nums[i]) {
                return vec![*e, i as i32];
            } else {
                cache.insert(remain, i as i32);
            }
        }
        Vec::new()
    }
}

#[cfg(test)]
mod test {

    use super::*;
    #[test]
    fn test_two_sum() {
        assert_eq!(Solution::two_sum(vec![2,7,11,15], 9), vec![0,1]);
        assert_eq!(Solution::two_sum(vec![3,2,4], 6), vec![1,2]);
        assert_eq!(Solution::two_sum(vec![3,3], 6), vec![0,1]);
    }

    #[test]
    fn test_two_sum2() {
        assert_eq!(Solution::two_sum2(vec![2,7,11,15], 9), vec![0,1]);
        assert_eq!(Solution::two_sum2(vec![3,2,4], 6), vec![1,2]);
        assert_eq!(Solution::two_sum2(vec![3,3], 6), vec![0,1]);
    }

    #[test]
    fn test_two_sum3() {
        assert_eq!(Solution::two_sum3(vec![2,7,11,15], 9), vec![0,1]);
        assert_eq!(Solution::two_sum3(vec![3,2,4], 6), vec![1,2]);
        assert_eq!(Solution::two_sum3(vec![3,3], 6), vec![0,1]);
    }

}